%A,b,c分别对应此题的不等式约束系数矩阵，不等式约束常数向量，目标函数系数向量
%Aeq   等式约束系数矩阵,   Beq    等式约束常数向量
%vlb   定义域的下界        vub    定义域的上界
%optXin   每次迭代的最优x   optF   每次迭代最优的f值  iter迭代次数
 
function [xstar, fxstar, flagOut, iter] = BranchBound1(c,A, b, Aeq, Beq, vlb, vub, optXin, optF, iter)
    global optX optVal optFlag;%将最优解定义为全局变量
    iter = iter + 1;
    optX = optXin; optVal = optF;%更新迭代得到的值
    % options = optimoptions("linprog", 'Algorithm', 'interior-point-legacy', 'display', 'none');
    
    [x, fit, status] = linprog(c,A, b, Aeq, Beq, vlb, vub, []);
    %status返回算法迭代停止原因
    %status = 1 算法收敛于解x，即x是线性规划的最优解
    if status ~= 1%没有找到最优解，此分支不用继续迭代下去，返回
        xstar = x;
        fxstar = fit;
        flagOut = status;
        return;
    end
    
    if max(abs(round(x) - x)) > 1e-3%找到的函数最优解仍不是整数解
        if fit > optVal   %此题求解的是max,此时的函数值大于之前解得的值
            xstar = x;
            fxstar = fit;
            flagOut = -100;
            return;
        end
        
    else%此时解得的函数解为整数解，此分支求解结束，不再继续向下求解，返回
        if fit > optVal   %此题求解的是max,此时的函数值大于之前解得的值
            xstar = x;
            fxstar = fit;
            flagOut = -101;
            return;
        else   %解出的值<之前解得的值，先放入全局变量中暂时存放
            optVal = fit;
            optX = x;
            optFlag = status;
            xstar = x;
            fxstar = fit;
            flagOut = status;
            return;
        end
    end
    midX = abs(round(x) - x);%得到x对应的小数部分
    notIntV = find(midX > 1e-3);%得到非整数的x的索引值，find()函数返回非0的索引值
    pXidx = notIntV(1);%得到第一个非整数x的下标索引
    tempVlb = vlb;%临时拷贝一份
    tempVub = vub;
    %fix(x) 函数将x中元素零方向取整
    if vub(pXidx) >= fix(x(pXidx)) + 1%原上界大于此时找到的分界的位置值
        tempVlb(pXidx) = fix(x(pXidx)) + 1;%将这个分界位置值作为新的下界参数传入，进一步递归
        [~, ~, ~] = BranchBound1(c,A, b, Aeq, Beq, tempVlb, vub, optX, optVal, iter + 1);
    end
    
    if vlb(pXidx) <= fix(x(pXidx))%原下界小于此时找到的分界的位置值
        tempVub(pXidx) = fix(x(pXidx));%将这个分界位置值作为新的上界参数传入，进一步递归
        [~, ~, ~] = BranchBound1(c,A, b, Aeq, Beq, vlb, tempVub, optX, optVal, iter + 1);
    end
    xstar = optX;
    fxstar = optVal;
    flagOut = optFlag;
end